<?php 
/** 
 * 从上往下打印二叉树
 * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 * 使用一个队列，每个节点出队，则它的左右子孩子入队
 */

class TreeNode{
    public $val;
    public $left = NULL;
    public $right = NULL;
    public function __construct($val){
        $this->val = $val;
    }
}

function PrintFromTopToBottom($root)
{
    $queue = [];
    if ($root == null) {
    	return null;
    }
    array_unshift($queue, $root);
    while (!empty($queue)) {
    	$node = array_pop($queue);
    	echo $node->val.' ';
    	if ($node->left) {
    		array_unshift($queue, $node->left);
    	}
    	if ($node->right) {
    		array_unshift($queue, $node->right);
    	}
    }
}

$node = new TreeNode(1);
$node->left = new TreeNode(2);
$node->right = new TreeNode(3);
$node->left->left = new TreeNode(4);
$node->left->right = new TreeNode(5);
$node->right->left = new TreeNode(6);
$node->right->right = new TreeNode(7);

PrintFromTopToBottom($node);
